/*
题目: 到达角落需要移除障碍物的最小数目
给你一个下标从 0 开始的二维整数数组 grid ，数组大小为 m x n 。每个单元格都是两个值之一：

    0 表示一个 空 单元格，
    1 表示一个可以移除的 障碍物 。

你可以向上、下、左、右移动，从一个空单元格移动到另一个空单元格。

现在你需要从左上角 (0, 0) 移动到右下角 (m - 1, n - 1) ，返回需要移除的障碍物的 最小 数目。

https://leetcode.cn/problems/minimum-obstacle-removal-to-reach-corner
 */
public class MinimumObstacles {
    private static final int INF = Integer.MAX_VALUE;
    int[] dir = new int[] {0, -1, 0, 1, 0};

    public int minimumObstacles(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;

        // 从起点到达 [i][j] 时移除的最小障碍物数量
        int[][] dis = new int[row][col];
        for (int i = 0; i < row; i ++) Arrays.fill(dis[i], INF);

        Deque<int[]> deque = new LinkedList<> ();
        deque.offerLast(new int[] {0, 0});
        dis[0][0] = 0; // 没有障碍物

        while (!deque.isEmpty()) {
            int[] p = deque.poll();
            for (int i = 0; i < 4; i ++) {
                int nextX = p[0] + dir[i];
                int nextY = p[1] + dir[i + 1];
                if (nextX < 0 || nextX >= row || nextY < 0 || nextY >= col)  continue ;

                // 这里也有去重的作用, 存在更小的路径才去更新, 而 "循环的情况" 又不能更短
                if (dis[p[0]][p[1]] + grid[nextX][nextY] < dis[nextX][nextY]) {
                    dis[nextX][nextY] = dis[p[0]][p[1]] + grid[nextX][nextY];
                    //  如果没有障碍物, 那么优先进入队头, 优先搜索
                    if (grid[nextX][nextY] == 0) deque.offerFirst(new int[] {nextX, nextY});
                    else                        deque.offerLast(new int[] {nextX, nextY});
                }
            }
        }

        return dis[row - 1][col - 1];
    }
}
